//#include "header.h"	//AnycodeX includes the header.h by default, needn't cancle the notation.
#include <iostream>
#include <time.h>
#include <stdlib.h>
#include <iterator>
using namespace std;
#define SIZE (20)
class sort_base
{
public:
    virtual void sort(int a[SIZE], int size) = 0;
};

class Quicksort : public sort_base
{
    void sort(int a[], int left, int right);

public:
    void sort(int a[], int size);
};

void Quicksort::sort(int a[], int left, int right)
{
    if (left >= right)
        return;
    int i = left, j = right;
    while (i < j)
    {
        while (i < j && a[j] >= a[left])
            j--;
        while (i < j && a[i] <= a[left])
            i++;
        swap(a[i], a[left]);
        sort(a, left, i - 1);
        sort(a, i + 1, right);
    }
}

void Quicksort::sort(int a[], int size)
{
    sort(a, 0, size - 1);
}

class testcase_for_sort
{
public:
    static void test(sort_base &input)
    {
        srand(time(NULL));
        int a[SIZE];
        for (int i = 0; i < SIZE; i++)
        {
            a[i] = rand() % 200;
        }
        ostream_iterator<int> it(cout, " ");
        copy(a, a + SIZE, it);
        cout << endl;
        input.sort(a, SIZE);
        copy(a, a + SIZE, it);
    }
};

class Mergesort : public sort_base
{
public:
    void sort(int a[], int size)
    {
        int *tmp = new int(size);
        merge(a, 0, size - 1, tmp);
    }
    void merge_array(int a[], int left, int mid, int right, int *tmp)
    {
        int i = left, j = mid + 1, k = 0;
        while (i <= mid && j <= right)
        {
            tmp[k++] = a[i] < a[j] ? a[i++] : a[j++];
        }
        while (i <= mid)
        {
            tmp[k++] = a[i++];
        }
        while (j <= right)
        {
            tmp[k++] = a[j++];
        }
        for (int i = 0; i < k; i++)
        {
            a[left + i] = tmp[i];
        }
    }
    void merge(int a[], int left, int right, int tmp[])
    {
        if (left >= right)
            return;
        merge(a, left, (left + right) / 2, tmp);
        merge(a, (left + right) / 2 + 1, right, tmp);
        merge_array(a, left, (left + right) / 2, right, tmp);
    }
};

int main()
{
    Mergesort solution;

    testcase_for_sort::test(solution);
    return 0;
}